\documentclass[a4paper,11pt]{article}
\usepackage[utf8x]{inputenc}
\usepackage[croatian]{babel}
\usepackage{amsmath,amsfonts,amsthm}
\usepackage{url}
\usepackage{xmpincl}
\includexmp{metadata}

\title{Natjecateljsko programiranje \\ 0. predavanje}
\date{12.09.2009.}

\begin{document}
\maketitle
\tableofcontents
\pagebreak

\section{Analiza prijemnog ispita}
Napisat ću i obrazložiti rješenja zadataka (proširenih i originalnih) koji
su se pojavili na prijemnom. Zadaci nisu bili toliko teški, no dane su i
ideje kako da ih se oteža.

Naravno, shvatiti rješenje je mnogo lakše nego ga smisliti. Još je lakše
ako vam ga netko uživo objasni. Ukoliko niste sami pokušali riješiti
zadatak -- pokušajte. Pogotovo pokušajte riješiti teže verzije. A uvijek
možete i sami otežati zadatak, promijeniti neke uvjete i sl.

\subsection{Zadatak: Robinson}
Ovaj zadatak nije tražio mnogo razmišljanja. Potrebno je samo
implementirati simulaciju kretanja kuglice po zadanim pravilima. 

Na ulazu su dane dimenzije ploče ($R, S < 100$), opis ploče i broj trenutaka
tj. pomaka kuglice ($T < 1000$). Ukoliko se simulira svaki korak onda je
složenost algoritma $O(T)$.

\subsubsection*{Teža verzija}
Zadatak može postati zanimljiviji ukoliko promijenimo ograničenje
za $T$ npr. $T<10^{18}$. U tom slučaju bi završetak prijašnjeg algoritma
čekali par stotina godina što ne zvuči baš praktično.

Pitanje je trebamo li uopće simulirati sve korake? Broj polja u kojima 
se kuglica može naći je sigurno manji od $R \cdot S = 10^4$ 
što je opet puno manje od $T$.
Dakle, nakon nekog vremena kuglica će sigurno \emph{posjetiti} već prije
posjećeno polje. Nakon toga će početi ponavljati jedan te isti ciklus
koraka (jer sljedeći korak ne ovisi o prošlim). Mi te cikluse ne moramo
simulirati. Označimo duljinu ciklusa sa $T_c$, a preostalo vrijeme nakon
što posjetimo već posjećeno polje sa $T_p$.

Nakon cijelog ciklusa kuglica je opet u istom polju. 
Takvih cijelih ciklusa ima $\lfloor T_p / T_c \rfloor$, a nas zanima
ostatak dijeljenja $T_p$ sa $T_c$. Taj broj koraka ćemo odsimulirati
i naći se u polju u kojem bi se našli i nakon preostalih $T_p$ koraka.

\subsubsection*{Implementacija}
Za težu verziju moramo koristiti pomoćnu matricu u kojoj ćemo 
pratiti redni broj koraka u kojem smo posjetili odgovarajuće polje. 
Zašto redni broj, a ne samo zastavicu da smo posjetili -- 
jer ćemo na temelju toga izračunati duljinu ciklusa.
Primjerice, ako ponovno posjetimo neko polje u 7. koraku, a u pomoćnoj
matrici piše da smo ga već posjetili u 3. onda je duljina ciklusa 4.

Nakon što uđemo u ciklus samo izračunamo koliko još koraka
moramo simulirati. Time ćemo preskočiti nepotrebno simuliranje
cijelih ciklusa. Sve ostalo je jedanko kao i u početnom zadatku.

\subsection{Zadatak: Umnožak}
Ovdje je potrebno uočiti strategiju kojom ćemo uvećavati brojeve.
Nakon malo isprobavanja možemo primijetiti da je uvijek najbolje uvećati
najmanji broj. Kako bi to arugmentirali?

\subsubsection*{Dokaz}
Sami se uvjerite da je u \emph{jednom koraku} najbolje uvećati najmanji broj.
Možemo primijeniti "greedy" strategiju i u svakom od $k$ koraka uvećati najmanji
tj. učiniti ono što je najbolje u tom trenutku.

Takav pristup je često kriv pa je dobro da se čvrsto uvjerimo u njegovu točnost.
Ovdje možda i nije bilo toliko bitno, no općenito je to dobro učiniti.

Dakle, u nekom optimalnom izboru uvećanja sigurno postoji korak u kojem uvećavamo najmanji broj.
Zašto? Nakon $(k-1)$ uvećanja preostane nam još jedno, a tu je najbolje uvećati upravo
najmanji broj. 

Redosljed uvećavanja nije bitan pa onda možemo najmanji uvećati odmah. Nakon toga se
nalazimo pred sličnim problemom sa $(k-1)$ uvećanjem. Tu primijenimo slično razmišljanje.

\subsubsection*{Implementacija}
Prvo ćemo sortirati brojeve. Moramo pamtiti i njihov redni broj jer
se traži ispis u jednakom redosljedu u kojem su bili na početku.

Zatim se krećemo po sortiranom nizu. Kad naiđemo na broj različit od prethodnog --
\emph{sve} prethodne uvećamo na njegovu razinu. Naravno, zbog ograničenog
broja uvećanja to nećemo moći uvijek napraviti. U tom slučaju uvećamo
\emph{sve zajedno} koliko možemo (na istu razinu), a ostatak uvećanja
ravnomjerno raspodijelimo.

Postoji još jedan detalj. Nije potrebno doslovno uvećati sve prethodne brojeve.
Dovoljno je pamtiti na koju razinu bi ih uvećali, a kasnije to obaviti u jednom
prolazu. Inače bi složenost ovog dijela bila $O(N^2)$ što je presporo jer je $N \leq 10^5$

Konačno, takav algoritam radi u vremenu $O(N\log{N})$ zbog sortiranja.

\subsection{Zadatak: Ispit}
Ovaj zadatak je bio vrlo jednostavan. Nešto teža verzija je zadana
u domaćoj zadaći.

\subsection{Zadatak: Unija}
Ovdje je zadano $N \leq 10^5$ \emph{zatvorenih} intervala i potrebno
je odrediti broj prirodnih brojeva u njihovoj uniji. Granice intervala
su prirodni brojevi manji od $10^9$. 

Očito je da će algoritam kvadratne složenosti $O(N^2)$ raditi presporo. Takav
bi algoritam možda mogao uspoređivati međusobno intervale i spajati ih ukoliko se
presjecaju. Sada ćemo vidjeti rješenje koje je mnogo brže i elegantnije 
za impementirati.

Prvo sortiramo intervale po donjoj granici. To možemo obaviti u \\ $O(N \log{N})$.
Nakon toga prođemo jednom kroz tako sortiran niz što je $O(N)$ operacija. 
Usput pamtimo i gornju granicu \emph{dosadašnje unije} (samo nas to zanima, 
izgled cijele unije nije bitan). 
Kad posjetimo $k$-ti interval moguća su tri slučaja:
\begin{itemize}
	\item $k$-ti interval se nalazi u potpunosti unutar dosadašnje unije
	pa ne pridonosi traženom broju prirodnih brojeva.
	\item $k$-ti interval se djelomično nalazi unutar dosadašnje unije.
    Tu pribrojimo samo ono što je izvan ondnosno zanemarimo ono što je u presjeku. 
	I postavimo gornju granicu dosadašnje unije na gornju granicu $k$-tog intervala.
	\item $k$-ti interval se nalazi u potpunosti izvan dosadašnje unije.
	U tom slučaju jednostavno pribrojimo sve brojeve iz tog intervala.
	I opet popravimo gornju granicu dosadašnje unije.
\end{itemize}
Nije moguće da $k$-ti interval prekrije neku "prazninu" od prije jer 
je njegova donja granica sigurno veća ili jednaka od donje granice $(k-1)$-tog
intervala (pošto su tako sortirani). Složenost je dakle $O(N\log{N})$ i to radi
ko zmaj.

\subsubsection*{Nešto drugačije rješenje}
Filip je na satu pokazao malo drugačije rješenje koje se zasniva na
nešto općenitijoj ideji o kojoj će biti više riječi kasnije.

\subsection{Zadatak: Kolekcija}
U ovom zadatku je potrebno odrediti postoji li podskup
zadanog skupa vektora (oglasi) čija je suma elemenata jednaka traženom
vektoru (Mirkova kolekcija).

Uočimo da je $N \leq 20$ (broj oglasa). Prema tome, broj svih podskupova
je najviše $2^{20} \approx 10^6$ pa jednostavno isprobamo sve
mogućnosti i provjerimo postoji li traženi podskup. Složenost je $O(2^NN)$.

Mnogo bolji algoritam nije poznat pošto je taj problem NP-potpun. 

\subsubsection*{Implementacija}
Problem je konstruirati sve moguće podskupove. Svakom podskupu
odgovara \emph{boolean} niz duljine $N$ u kojem $k$-ti element
kaže nalazi li se $k$-ti vektor u tom podskupu. Ta ideja vam
je vjerojatno poznata i od prije.

Te nizove možemo konstruirati rekurzivno ili možemo iskoristiti
\emph{bitwise} operatore i petlju koja ide od $0$ do $2^N$. Kako?

\subsubsection*{Teža verzija}
Da je $N$ recimo bio $35$ onda bi morali biti lukaviji. $2^{35} \approx 10^{10}$ što
je previše da isprobamo sve mogućnosti.
Evo \emph{copy-paste} sa Wikipedije
\footnote{\url{http://en.wikipedia.org/wiki/Subset_sum#Exponential_time_algorithm}} 
o algoritmu koji radi u vremenu $O(2^{N/2}N)$:
\begin{quote}
A better exponential time algorithm is known, which runs in time $O(2^{N/2}N)$. 
The algorithm splits arbitrarily the $N$ elements into two sets of $N/2$ each. 
For each of these two sets, it calculates sums of all $2^{N/2}$ possible 
subsets of its elements and stores them in an array of length $2^{N/2}$. 
It then sorts each of these two arrays, which can be done in time $O(2^{N/2}N)$. 
When arrays are sorted, the algorithm can check if an element of the first 
array and an element of the second array sum up to $s$ in time $O(2^{N/2})$. 
To do that, the algorithm passes through the first array in decreasing order 
(starting at the largest element) and the second array in increasing order 
(starting at the smallest element). 
Whenever the sum of the current element in the first array and the current element 
in the second array is more than $s$, the algorithm moves to the next element in 
the first array. 
If it is less than $s$, the algorithm moves to the next element in the second array. 
If two elements with sum $s$ are found, it stops. 
No better algorithm has been found since Horowitz and Sahni first published 
this algorithm in 1974.
\end{quote}

\end{document}
